package RandomTest1;

import java.util.Scanner;
import java.util.Stack;

public class LeetCode20 {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        String s = input.nextLine();
        System.out.println(isValid(s));
    }

    /**
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
     * 有效字符串需满足：
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     *
     * @param s
     * @return
     */
    public static boolean isValid(String s) {
        Stack stack = new Stack();
        //1.左括号全部入栈
        //2.判断是否有左括号，没有直接返回false
        //3.遇到左括号进行全部压栈
        //4.如果遇到右括号则出栈，然后进行判断，不符合则返回
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '[' || s.charAt(i) == '(' || s.charAt(i) == '{') {
                stack.push(s.charAt(i));
            } else {
                if (stack.isEmpty()) {
                    return false;
                } else if (s.charAt(i) == ']' && (char) stack.pop() != '[') {
                    return false;
                } else if (s.charAt(i) == '}' && (char) stack.pop() != '{') {
                    return false;
                } else if (s.charAt(i) == ')' && (char) stack.pop() != '(') {
                    return false;
                }
            }
        }
        // 第一种情况：此时我们已经遍历完了字符串，
        // 但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
        return stack.isEmpty();
    }
}
